翻訳と辞書 Words near each other ・ Congriscus megastomus ・ Congro Volcanic Fissural System ・ Congrogadus subducens ・ Congrosoma evermanni ・ Congrove Field and The Tumps ・ Congrua ・ Congrua portio ・ Congruence ・ Congruence (general relativity) ・ Congruence (geometry) ・ Congruence (manifolds) ・ Congruence bias ・ Congruence coefficient ・ Congruence ideal ・ Congruence lattice problem ・ Congruence of squares ・ Congruence of triangles ・ Congruence principle ・ Congruence relation ・ Congruence subgroup ・ Congruence-permutable algebra ・ Congruent isoscelizers point ・ Congruent melting ・ Congruent number ・ Congruent transformation ・ Congruum ・ Congrès de la Culture Francaise en Floride ・ Congrès International d'Architecture Moderne ・ Congrès Panafricain des Jeunes et des Patriotes ・ Congrégation des témoins de Jéhovah de St-Jérôme-Lafontaine v Lafontaine (Village of) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Congruence of squares ： ウィキペディア英語版 Congruence of squares In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. ==Derivation== Given a positive integer ''n'', Fermat's factorization method relies on finding numbers ''x'', ''y'' satisfying the equality :$x^2\; -\; y^2\; =\; n\backslash ,\backslash !$ We can then factor ''n'' = ''x''2 - ''y''2 = (''x'' + ''y'')(''x'' - ''y''). This algorithm is slow in practice because we need to search many such numbers, and only a few satisfy the strict equation. However, ''n'' may also be factored if we can satisfy the weaker congruence of squares condition: :$x^2\; \backslash equiv\; y^2\; \backslash pmod\; \backslash hbox\; x\; \backslash not\backslash equiv\; \backslash pm\; y\; \backslash pmod$. From here we easily deduce :$x^2\; -\; y^2\; \backslash equiv\; 0\; \backslash pmod\; \backslash hbox\; (x\; +\; y)(x\; -\; y)\; \backslash equiv\; 0\; \backslash pmod$ This means that ''n'' divides the product (''x'' + ''y'') (''x'' - ''y''), but since we also require ''x'' ≠ ±''y'' (mod ''n''), ''n'' divides neither (x+y) nor (x−y) alone. Thus (''x'' + ''y'') and (''x'' − ''y'') each contain proper factors of ''n''. Computing the greatest common divisors of (''x'' + ''y'',''n'') and of (''x'' - ''y'',''n'') will give us these factors; this can be done quickly using the Euclidean algorithm. Congruences of squares are extremely useful in integer factorization algorithms and are extensively used in, for example, the quadratic sieve, general number field sieve, continued fraction factorization, and Dixon's factorization. Conversely, because finding square roots modulo a composite number turns out to be probabilistic polynomial-time equivalent to factoring that number, any integer factorization algorithm can be used efficiently to identify a congruence of squares. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Congruence of squares」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.